package io.github.handyang.algorithms.search;

import java.util.LinkedList;
import java.util.List;

/**
 * 基于拉链法的Hash表
 */
public class LinkHashST<K, V> implements SymbolTable<K, V> {

    Node[] table;

    int size;

    double loadFactor = 0.7;

    public LinkHashST() {
        init();
    }

    @Override
    public void put(K key, V value) {
        reSize();

        int hash = hash(key);
        int index = hash & (this.table.length - 1);
        if (this.table[index] == null) {
            this.table[index] = new Node(key, value, hash);
            this.size++;
        } else {
            Node cursor = this.table[index];
            while (cursor.next != null) {
                if (cursor.key.equals(key)) {
                    cursor.value = value;
                    break;
                }

                cursor = cursor.next;
            }

            if (cursor.key.equals(key)) {
                cursor.value = value;
            } else {
                cursor.next = new Node(key, value, hash);
                this.size++;
            }
        }
    }

    @Override
    public V get(K key) {
        int hash = hash(key);
        int index = hash & (this.table.length - 1);

        Node cursor = this.table[index];
        while (cursor != null && !cursor.key.equals(key)) {
            cursor = cursor.next;
        }

        if (cursor != null) return (V) cursor.value;

        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterable<K> keys() {
        List<K> keys = new LinkedList<>();

        for (Node node : table) {
            Node cursor = node;

            while (cursor != null) {
                keys.add((K) cursor.key);
                cursor = cursor.next;
            }
        }

        return keys;
    }

    @Override
    public void clear() {
        init();
    }

    private int hash(K key) {
        if (key == null) return 0;

        return key.hashCode() ^ (key.hashCode() >> 16);
    }

    private void reSize() {
        if (size < this.table.length * loadFactor) {
            return;
        }

        //重建数组
        Node[] newTable = new Node[this.table.length << 1];
        for (Node head : table) {
            Node cursor = head;

            while (cursor != null) {
                Node next = cursor.next;
                cursor.next = null;

                int index = cursor.hash & (newTable.length - 1);

                if (newTable[index] == null) {
                    newTable[index] = cursor;
                } else {
                    Node linkCursor = newTable[index];
                    while (linkCursor.next != null) linkCursor = linkCursor.next;

                    linkCursor.next = cursor;
                }

                cursor = next;
            }
        }

        this.table = newTable;
    }

    private void init() {
        this.table = new Node[16];
        this.size = 0;
    }

    private final static class Node<K, V> {
        final int hash;

        final K key;
        V value;

        Node<K, V> next;

        public Node(K key, V value, int hash) {
            this.key = key;
            this.hash = hash;
            this.value = value;
        }
    }
}
